package qmlt.dataset.filter;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import qmlt.dataset.utils.EntropyUtils;

public class MultiWayDiscretizingFilter extends DiscretizingFilter
{
    private final InfoGainDiscretizingFilter infoGainDescretizer = new InfoGainDiscretizingFilter();
		private List<Float>	dividers = null;

    @Override
    public List<Float> getDividers(List<Float> values, List<Object> classes)
    {
	    	if (dividers != null)
	    		return dividers;
	    	
        dividers = new ArrayList<Float>();

        List<Float> helperDividers = infoGainDescretizer.getDividers(values, classes);
        if (helperDividers.size() > 0)
        {
            float dp = helperDividers.get(0);
            int divide = 0; // will point to the position AFTER divide point
            while (values.get(divide) < dp)
                divide++;

            int n = values.size();
            float beforeEntropy = EntropyUtils.calculateEntropy(classes);

            List<Float> subv1 = values.subList(0, divide);
            List<Float> subv2 = values.subList(divide, n);
            List<Object> subc1 = classes.subList(0, divide);
            List<Object> subc2 = classes.subList(divide, n);
            float infoGain = EntropyUtils.calculateInfoGain(n, beforeEntropy, subc1, subc2);

            int k = getClassCount(classes);
            int k1 = getClassCount(subc1);
            int k2 = getClassCount(subc2);
            float ent1 = EntropyUtils.calculateEntropy(subc1);
            float ent2 = EntropyUtils.calculateEntropy(subc2);

            float delta = log2(Math.pow(3, k) - 2) - k * beforeEntropy + k1 * ent1 + k2 * ent2;
            float minGain = (log2(n - 1) + delta) / n;

            if (infoGain > minGain)
            {
                // accept the divide
                List<Float> d1 = getDividers(subv1, subc1);
                List<Float> d2 = getDividers(subv2, subc2);
                dividers.addAll(d1);
                dividers.add(dp);
                dividers.addAll(d2);
                Collections.sort(dividers);
            }
        }

        return dividers;
    }

    public int getClassCount(List<Object> classes)
    {
        Set<Object> set = new HashSet<Object>();
        for (Object c : classes)
        {
            set.add(c);
        }
        return set.size();
    }

    private float log2(double d)
    {
        return (float) EntropyUtils.log2(d);
    }
}
